EE364A Lecture 5 and Lecture 6

课程主页：https://see.stanford.edu/Course/EE364A

这次回顾凸优化第五，第六讲，这部分介绍了凸优化问题。

Lecture 5 and Lecture 6 Convex optimization problems

优化问题的标准形式

$$\begin{array}{cl}{ {\operatorname{minimize} } } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {h_{i}(x)=0, \quad i=1, \ldots, p}\end{array}$$

• $x \in \mathbf{R}^{n}$为优化变量
• $f_{0} : \mathbf{R}^{n} \rightarrow \mathbf{R}$为目标或损失函数
• $f_{i} : \mathbf{R}^{n} \rightarrow \mathbf{R}, i=1, \dots, m$，为不等式约束
• $h_{i} : \mathbf{R}^{n} \rightarrow \mathbf{R}$为等式约束

最优值

$$p^{\star}=\inf \left\{f_{0}(x) | f_{i}(x) \leq 0, i=1, \ldots, m, h_{i}(x)=0, i=1, \ldots, p\right\}$$

• 如果问题是不可行（没有$x$满足约束），那么$p^{\star}=\infty$
• 如果问题无下界，那么$p^{\star}=-\infty$

最优和局部最优点

$x$是可行的，如果$x \in \operatorname{dom} f_{0}$并且满足约束。

一个可行的$x$是最优的，如果$f_{0}(x)=p^{\star}$；$X_{\mathrm{opt} }$是最优点构成的集合。

$x$是局部最优的，如果存在$R>0$，使得$x$为满足如下条件的最优点：

$$\begin{array}{ll}{\operatorname{minimize}(\text {over } z)} & {f_{0}(z)} \\ {\text { subject to } } & {f_{i}(z) \leq 0, \quad i=1, \ldots, m, \quad h_{i}(z)=0, \quad i=1, \ldots, p} \\ {} & {\|z-x\|_{2} \leq R}\end{array}$$

例子（$n=1, m=p=0$）

• $f_{0}(x)=1 / x, \operatorname{dom} f_{0}=\mathbf{R}_{++} : p^{\star}=0$，无最优点
• $f_{0}(x)=-\log x, \operatorname{dom} f_{0}=\mathbf{R}_{++} : p^{\star}=-\infty$
• $f_{0}(x)=x \log x, \operatorname{dom} f_{0}=\mathbf{R}_{++} : p^{\star}=-1 / e$，$x=1/e$最优
• $f_{0}(x)=x^{3}-3 x, p^{\star}=-\infty$，在$x=1$局部最优

隐式约束

标准优化问题有隐式约束

$$x \in \mathcal{D}=\bigcap_{i=0}^{m} \operatorname{dom} f_{i} \cap \bigcap_{i=1}^{p} \operatorname{dom} h_{i}$$

• 我们称$\mathcal D$维问题的定义域
• 约束$f_{i}(x) \leq 0, h_{i}(x)=0$为显式约束
• 一个问题是无约束的，如果没有显示约束（$m=p=0$）

例子：

$$\text { minimize } f_{0}(x)=-\sum_{i=1}^{k} \log \left(b_{i}-a_{i}^{T} x\right)$$

上述问题为无约束问题，隐式约束为$a_{i}^{T} x<b_{i}$

可行性问题

$$\begin{array}{ll}{\text { find } } & {x} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {h_{i}(x)=0, \quad i=1, \ldots, p}\end{array}$$

上述问题可以被看出一般问题的特殊情形， 其中$f_0 (x)=0$：

$$\begin{array}{cl}{\operatorname{minimize} } & {0} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {h_{i}(x)=0, \quad i=1, \ldots, p}\end{array}$$

• $p^{\star}=0$如果约束可行；任何可行的$x$都是最有
• $p^{\star}=\infty$如果约束不可行

凸优化问题

标准凸优化问题：

$$\begin{array}{cl}{\operatorname{minimize} } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {a_{i}^{T} x=b_{i}, \quad i=1, \ldots, p}\end{array}$$

• $f_{0}, f_{1}, \ldots, f_{m}$为凸函数；等式约束为仿射
• 问题是拟凸的，如果$f_0$拟凸（并且$f_{1}, \ldots, f_{m}$凸）

上述问题常写成

$$\begin{array}{cl}{\operatorname{minimize} } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {A x=b}\end{array}$$

重要性质：凸优化问题的可行解为凸集。

例子：

$$\begin{array}{cl}{\underset{\text { subject to } }{\operatorname{minimize} } } & {f_{0}(x)=x_{1}^{2}+x_{2}^{2} } \\ {\text { subject to } } & {f_{1}(x)=x_{1} /\left(1+x_{2}^{2}\right) \leq 0} \\ {} & {h_{1}(x)=\left(x_{1}+x_{2}\right)^{2}=0}\end{array}$$

• $f_0$是凸集；可行集$\left\{\left(x_{1}, x_{2}\right) | x_{1}=-x_{2} \leq 0\right\}$是凸集

• 不是凸优化问题：$f_1$非凸，$h_1$不是仿射函数

• 等价于如下凸优化问题

  $$\begin{array}{cl}{\operatorname{minimize} } & {x_{1}^{2}+x_{2}^{2} } \\ {\text { subject to } } & {x_{1} \leq 0} \\ {} & {x_{1}+x_{2}=0}\end{array}$$

局部和全局最优

凸优化问题的局部最优点为（全局）最优。

证明：假设$x$局部最优，$y$是最优点并且$f_{0}(y)<f_{0}(x)$

$x$局部最优意味着存在$R>0$，使得

$$z \text { 可行, } \quad\|z-x\|_{2} \leq R \quad \Longrightarrow \quad f_{0}(z) \geq f_{0}(x)$$

考虑$z=\theta y+(1-\theta) x$，$\theta=R /\left(2|y-x|_{2}\right)$

• $|y-x|_{2}>R$，所以$0<\theta<1 / 2$

• $z$是两个可行点的凸组合，因此也是可行的

• $|z-x|_{2}=\theta| x-y | =\frac R 2$并且

  $$f_{0}(z) \leq \theta f_{0}(x)+(1-\theta) f_{0}(y)<f_{0}(x)$$

  这就与$x$局部最优矛盾

可微$f_0$的最优判别条件

$x$是最优的当且仅当其可行，并且

$$\nabla f_{0}(x)^{T}(y-x) \geq 0 \quad \text { 对所有可行} y$$

如果非零，$\nabla f_{0}(x)$定义了可行集合$X$在$x$的支撑超平面。

• 无约束问题：$x$是最优的当且仅当

  $$x \in \operatorname{dom} f_{0}, \quad \nabla f_{0}(x)=0$$

• 等式约束问题

  $$\text { minimize } f_{0}(x) \quad \text { subject to } \quad A x=b$$

  $x$最优当且仅当存在$\nu$使得

  $$x \in \operatorname{dom} f_{0}, \quad A x=b, \quad \nabla f_{0}(x)+A^{T} \nu=0$$

• 关于非负条件最小化

  $$\text { minimize } f_{0}(x) \quad \text { subject to } \quad x \succeq 0$$

  $x$最优当且仅当

  $$x \in \operatorname{dom} f_{0}, \quad x \succeq 0, \quad\left\{\begin{array}{ll}{\nabla f_{0}(x)_{i} \geq 0} & {x_{i}=0} \\ {\nabla f_{0}(x)_{i}=0} & {x_{i}>0}\end{array}\right.$$

等价凸优化问题

两个问题等价当且仅当解相同。

一些变换保凸：

• 消除等式约束

  $$\begin{array}{cl}{\operatorname{minimize} } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {A x=b}\end{array}$$

  等价于

  $$\begin{array}{ll}{\operatorname{minimize}(\text {over } z)} & {f_{0}\left(F z+x_{0}\right)} \\ {\text { subject to } } & {f_{i}\left(F z+x_{0}\right) \leq 0, \quad i=1, \ldots, m}\end{array}$$

  其中$F$和$x_0$满足

  $$A x=b \quad \Longleftrightarrow \quad x=F z+x_{0} \text { for some } z$$

• 引入等式约束

  $$\begin{array}{ll}{\operatorname{minimize} } & {f_{0}\left(A_{0} x+b_{0}\right)} \\ {\text { subject to } } & {f_{i}\left(A_{i} x+b_{i}\right) \leq 0, \quad i=1, \ldots, m}\end{array}$$

  等价于

  $$\begin{array}{ll}{\operatorname{minimize}\left(\text { over } x, y_{i}\right)} & {f_{0}\left(y_{0}\right)} \\ {\text { subject to } } & {f_{i}\left(y_{i}\right) \leq 0, \quad i=1, \ldots, m} \\ {} & {y_{i}=A_{i} x+b_{i}, \quad i=0,1, \ldots, m}\end{array}$$

• 对线性不等式引入松弛变量

  $$\begin{array}{ll} { {\operatorname{minimize} } } & {f_{0}(x)} \\ {\text { subject to} } & {a_{i}^{T} x \leq b_{i}, \quad i=1, \ldots, m}\end{array}$$

  等价于

  $$\begin{array}{cl}{\operatorname{minimize}(\text {over } x, s)} & {f_{0}(x)} \\ {\text { subject to } } & {a_{i}^{T} x+s_{i}=b_{i}, \quad i=1, \ldots, m} \\ {} & {s_{i} \geq 0, \quad i=1, \ldots m}\end{array}$$

• 上镜图：标准凸优化问题等价于

  $$\begin{array}{ll}{\operatorname{minimize}(\text { over } x, t)} & {t} \\ {\text { subject to } } & {f_{0}(x)-t \leq 0} \\ {} & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {A x=b}\end{array}$$

• 关于某些变量最小化

  $$\begin{array}{ll}{ {\operatorname{minimize} } } & {f_{0}\left(x_{1}, x_{2}\right)} \\ {\text { subject to } } & {f_{i}\left(x_{1}\right) \leq 0, \quad i=1, \ldots, m}\end{array}$$

  等价于

  $$\begin{array}{ll}{ {\operatorname{minimize} } } & {\tilde{f}_{0}\left(x_{1}\right)} \\ {\text { subject to } } & {f_{i}\left(x_{1}\right) \leq 0, \quad i=1, \ldots, m}\end{array}$$

  其中$\tilde{f}_{0}\left(x_{1}\right)=\inf _{x_{2} } f_{0}\left(x_{1}, x_{2}\right)$

拟凸优化问题

$$\begin{array}{cl}{\operatorname{minimize} } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {A x=b}\end{array}$$

其中$f_{0} : \mathbf{R}^{n} \rightarrow \mathbf{R}$拟凸，$f_{1}, \ldots, f_{m}$凸。这时可能存在局部最优点不是全局最优点。

$f_0$的下水平集表示：

如果$f_0$是拟凸函数，那么存在一族函数$\phi_t$使得：

• 对固定的$t$，$\phi_t(x)$关于$x$是凸函数

• $f_0$的$t$下水平集是$\phi_t$的$0$水平集，即

  $$f_{0}(x) \leq t \quad \Longleftrightarrow \quad \phi_{t}(x) \leq 0$$

例子

$$f_{0}(x)=\frac{p(x)}{q(x)}$$

$p$为凸，$q$为凹，以及在$\operatorname{dom} f_{0}$上有$p(x) \geq 0, q(x)>0$。

可以取$\phi_{t}(x)=p(x)-t q(x)$：

• 对$t\ge 0$，$\phi_t $关于$x$为凸集
• $p(x) / q(x) \leq t$当且仅当$\phi_{t}(x) \leq 0$

拟凸优化问题可以通过二分法求解。

线性规划（LP）

考虑线性规划问题

$$\begin{array}{cl}{\operatorname{minimize} } & {c^{T} x+d} \\ {\text { subject to } } & {G x \preceq h} \\ {} & {A x=b}\end{array}$$

线性规划问题为

• 目标函数以及约束函数为仿射函数的凸优化问题
• 可行集为多面体

例子

分段线性最小化

$$\text { minimize } \quad \max _{i=1, \ldots, m}\left(a_{i}^{T} x+b_{i}\right)$$

等价于LP

$$\begin{array}{ll}{\text { minimize } } & {t} \\ {\text { subject to } } & {a_{i}^{T} x+b_{i} \leq t, \quad i=1, \ldots, m}\end{array}$$

多面体的切比雪夫中心

多面体

$$\mathcal{P}=\left\{x | a_{i}^{T} x \leq b_{i}, i=1, \ldots, m\right\}$$

的切比雪夫中心为最大内切球的中心

$$\mathcal{B}=\left\{x_{c}+u |\|u\|_{2} \leq r\right\}$$

• $a_{i}^{T} x \leq b_{i}$对所有$x\in \mathcal B$当且仅当

  $$\sup \left\{a_{i}^{T}\left(x_{c}+u\right) |\|u\|_{2} \leq r\right\}=a_{i}^{T} x_{c}+r\left\|a_{i}\right\|_{2} \leq b_{i}$$

• 因此$x_c, r$可以通过求解LP来决定

  $$\begin{array}{ll}{\text { maximize } } & {r} \\ {\text { subject to } } & {a_{i}^{T} x_{c}+r\left\|a_{i}\right\|_{2} \leq b_{i}, \quad i=1, \ldots, m}\end{array}$$

线性分式规划

依然考虑优化问题

$$\begin{array}{cl}{\operatorname{minimize} } & {f_{0}(x)} \\ {\text { subject to } } & {G x \preceq h} \\ {} & {A x=b}\end{array}$$

线性分式规划

$$f_{0}(x)=\frac{c^{T} x+d}{e^{T} x+f}, \quad \operatorname{dom} f_{0}(x)=\left\{x | e^{T} x+f>0\right\}$$

• 该问题是拟凸优化问题；可以通过二分法求解

• 该问题等价于LP（变量为$y,z$）

  $$\begin{array}{cl}{\underset{\text { subject to } }{\operatorname{minimize} } } & {c^{T} y+d z} \\ {\text { subject to } } & {G y \preceq h z} \\ {} & {A y=b z} \\ {} & {e^{T} y+f z=1} \\ {} & {z \geq 0}\end{array}$$

广义线性分式规划

$$f_{0}(x)=\max _{i=1, \ldots, r} \frac{c_{i}^{T} x+d_{i} }{e_{i}^{T} x+f_{i} }, \quad \operatorname{dom} f_{0}(x)=\left\{x | e_{i}^{T} x+f_{i}>0, i=1, \ldots, r\right\}$$

该问题依然是拟凸优化问题；可以通过二分法求解。

二次规划（QP）

$$\begin{array}{cl}{\operatorname{minimize} } & {(1 / 2) x^{T} P x+q^{T} x+r} \\ {\text { subject to } } & {G x \preceq h} \\ {} & {A x=b}\end{array}$$

• $P \in \mathbf{S}_{+}^{n}$，所以目标函数为凸二次函数
• 在多面体上最小化凸二次函数

例子

最小二乘法

$$\text { minimize } \quad\|A x-b\|_{2}^{2}$$

• 解析解$x^{\star}=A^{\dagger} b$（$A^{\dagger}$是伪逆）
• 可以增加线性约束

二次约束二次规划（QCQP）

$$\begin{array}{cl}{\operatorname{minimize} } & {(1 / 2) x^{T} P_{0} x+q_{0}^{T} x+r_{0} } \\ {\text { subject to } } & {(1 / 2) x^{T} P_{i} x+q_{i}^{T} x+r_{i} \leq 0, \quad i=1, \ldots, m} \\ {} & {A x=b}\end{array}$$

• $P_i \in \mathbf{S}_{+}^{n}$，所以目标函数和约束为凸二次函数
• 如果$P_{1}, \ldots, P_{m} \in \mathbf{S}_{++}^{n}$，可行区域为$m$个椭球以及仿射集合的交集

二阶锥规划（SOCP）

$$\begin{array}{cl}{\operatorname{minimize} } & {f^{T} x} \\ {\text { subject to } } & {\left\|A_{i} x+b_{i}\right\|_{2} \leq c_{i}^{T} x+d_{i}, \quad i=1, \ldots, m} \\ {} & {F x=g}\end{array}$$

其中$\left(A_{i} \in \mathbf{R}^{n_{i} \times n}, F \in \mathbf{R}^{p \times n}\right)$

• 不等式被称为二阶锥约束：

  $$\left(A_{i} x+b_{i}, c_{i}^{T} x+d_{i}\right) \in \mathbf{R}^{n_{i}+1}中的二阶锥$$

• 如果$n_i =0$，那么问题退化为LP；如果$c_i =0$，问题退化为QCQP

鲁棒线性规划

优化问题中的参数通常有不确定性，例如在LP中

$$\begin{array}{ll}{\text { minimize } } & {c^{T} x} \\ {\text { subject to } } & {a_{i}^{T} x \leq b_{i}, \quad i=1, \ldots, m}\end{array}$$

$c,a_i, b_i$可能有不确定性。

两种处理不确定性的常见方法（以$a_i$为例）：

• 确定性模型：约束对所有$a_{i} \in \mathcal{E}_{i}$成立

  $$\begin{array}{ll}{\text { minimize } } & {c^{T} x} \\ {\text { subject to } } & {a_{i}^{T} x \leq b_{i} \text { for all } a_{i} \in \mathcal{E}_{i}, \quad i=1, \ldots, m}\end{array}$$

• 随机模型：$a_i$是随机变量；约束以$\eta$的概率成立

  $$\begin{array}{ll}{ {\operatorname{minimize} } } & {c^{T} x} \\ {\text { subject to } } & {\operatorname{prob}\left(a_{i}^{T} x \leq b_{i}\right) \geq \eta, \quad i=1, \ldots, m}\end{array}$$

通过SOCP处理确定性模型

• 选择$\mathcal E _i$为椭球：

  $$\mathcal{E}_{i}=\left\{\overline{a}_{i}+P_{i} u |\|u\|_{2} \leq 1\right\} \quad\left(\overline{a}_{i} \in \mathbf{R}^{n}, \quad P_{i} \in \mathbf{R}^{n \times n}\right)$$

  中心为$\bar a_i$，半轴由$P_i$的奇异值决定

• 鲁棒LP

  $$\begin{array}{ll}{\text { minimize } } & {c^{T} x} \\ {\text { subject to } } & {a_{i}^{T} x \leq b_{i} \quad \forall a_{i} \in \mathcal{E}_{i}, \quad i=1, \ldots, m}\end{array}$$

  等价于SOCP

  $$\begin{array}{ll}{\operatorname{minimize} } & {c^{T} x} \\ {\text { subject to } } & {\overline{a}_{i}^{T} x+\left\|P_{i}^{T} x\right\|_{2} \leq b_{i}, \quad i=1, \ldots, m}\end{array}$$

  上述事实是因为

  $$\sup _{\|u\|_{2} \leq 1}\left(\overline{a}_{i}+P_{i} u\right)^{T} x=\overline{a}_{i}^{T} x+\left\|P_{i}^{T} x\right\|_{2}$$

通过SOCP处理随机模型

• 假设$a_{i} \sim \mathcal{N}\left(\bar{a}_{i}, \Sigma_{i}\right)$

• 那么$a_i^T x\sim \mathcal N(\bar a_i^T x, x^T \Sigma_i x)$，因此

  $$\operatorname{prob}\left(a_{i}^{T} x \leq b_{i}\right)=\Phi\left(\frac{b_{i}-\overline{a}_{i}^{T} x}{\left\|\Sigma_{i}^{1 / 2} x\right\|_{2} }\right)$$

• 鲁棒LP

  $$\begin{array}{ll}{\text { minimize } } & {c^{T} x} \\ {\text { subject to } } & {\text { prob }\left(a_{i}^{T} x \leq b_{i}\right) \geq \eta, \quad i=1, \ldots, m}\end{array}$$

  其中$\eta \ge 1/ 2$等价于SOCP

  $$\begin{array}{ll}{\text { minimize } } & {c^{T} x} \\ {\text { subject to } } & {\overline{a}_{i}^{T} x+\Phi^{-1}(\eta)\left\|\Sigma_{i}^{1 / 2} x\right\|_{2} \leq b_{i}, \quad i=1, \ldots, m}\end{array}$$

几何规划

单项式函数

$$f(x)=c x_{1}^{a_{1} } x_{2}^{a_{2} } \cdots x_{n}^{a_{n} }, \quad \operatorname{dom} f=\mathbf{R}_{++}^{n}$$

其中$c>0, \alpha_i \in \mathbf R$

多项式函数

$$f(x)=\sum_{k=1}^{K} c_{k} x_{1}^{a_{1 k} } x_{2}^{a_{2 k} } \cdots x_{n}^{a_{n k} }, \quad \operatorname{dom} f=\mathrm{R}_{++}^{n}$$

几何规划（GP）

$$\begin{array}{cl}{\operatorname{minimize} } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 1, \quad i=1, \ldots, m} \\ {} & {h_{i}(x)=1, \quad i=1, \ldots, p}\end{array}$$

其中$f_i $是多项式，$h_i$是单项式

凸形式的几何规划

令$y_i =\log x_i$，那么

• 单项式$f(x)=c x_{1}^{a_{1} } \cdots x_{n}^{a_{n} }$转换成

  $$\log f\left(e^{y_{1} }, \ldots, e^{y_{n} }\right)=a^{T} y+b \quad(b=\log c)$$

• 多项式$f(x)=\sum_{k=1}^{K} c_{k} x_{1}^{a_{1 k} } x_{2}^{a_{2 k} } \cdots x_{n}^{a_{n k} }$转换成

  $$\log f\left(e^{y_{1} }, \ldots, e^{y_{n} }\right)=\log \left(\sum_{k=1}^{K} e^{a_{k}^{T} y+b_{k} }\right) \quad\left(b_{k}=\log c_{k}\right)$$

• 几何规划转换成凸问题

  $$\begin{array}{cl}{\operatorname{minimize} } & {\log \left(\sum_{k=1}^{K} \exp \left(a_{0 k}^{T} y+b_{0 k}\right)\right)} \\ {\text { subject to } } & {\log \left(\sum_{k=1}^{K} \exp \left(a_{i k}^{T} y+b_{i k}\right)\right) \leq 0, \quad i=1, \ldots, m} \\ {} & {G y+d=0}\end{array}$$